package basic.courseLearn09.problem;

import org.junit.Test;

//背包问题
public class BagProblem {

    @Test
    public void test(){
        int[] weights = {2,3,4,5,9,7};
        int[] values = {3,4,5,8,10,6};
        int bag = 15;
        int max = solution_1(bag,0,weights,values);
        System.out.println(max);
    }

    /**
     * 背包问题，返回当前的最大值
     * @param bag 背包容量
     * @param i 当前物品的索引
     * @param weights 物品的重量数组
     * @param values  物品的价值数组
     * @return 最大价值
     */
    public Integer solution_1(int bag,int i ,int[] weights,int[] values){
        //1. 递归截止条件
        if(i>=weights.length || bag<0){
            return 0;
        }
        //2. 判断是否能够选择
        if (weights[i] <= bag){
            int value1 = values[i] + solution_1(bag-weights[i],i+1,weights,values);
            int value2 = solution_1(bag,i+1,weights,values);
            return Math.max(value1,value2);
        }else {
            return solution_1(bag,i+1,weights,values);
        }
    }


}
